package study.datastructure.link.leetcode;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-10-09 19:58
 */

/**
 2024/10/9,
 */

//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
public class Client206 {
    //1>2>3>4>5   5>4>3>2>1
    //head
    // prev curr   next
    //head

    /**
     * 构造一个新链表,从旧链表依次拿到每个节点,创建新的节点添加到新链表头部,完成后新链表即是倒叙的
     * @param head 头节点
     * @return 反转头节点
     */
    public  ListNode reverseList(ListNode head) {
        ListNode prev=null;
        ListNode curr=head;
        while (curr!=null){
           /* ListNode nextTemp=curr.next;
            curr.next=prev;
            prev=curr;
            curr=nextTemp;*/
            prev=new ListNode(curr.val,prev); //addFirst(val)
            curr=curr.next;
        }
        return prev;
    }

    /**
     * 递归 找到尾节点 尾回溯 改指向 最后解决死循环
     * @param head
     * @return
     */
    public  ListNode recursionToReverseList(ListNode head) {
       if (head==null||head.next==null){
           return head;
       }
      ListNode theLast=recursionToReverseList(head.next);//找到尾节点
       head.next.next=head; //改指向
       head.next=null;//最后解决死循环
      return theLast;
    }

    public static void main(String[] args) {
        ListNode t5=new ListNode(5,null);
        ListNode t4=new ListNode(4,t5);
        ListNode t3=new ListNode(3,t4);
        ListNode t2=new ListNode(2,t3);
        ListNode t1=new ListNode(1,t2);
        System.out.println(t1);
        /*ListNode reverse=new Client206().reverseList(t1);
        System.out.println(reverse);*/
        System.out.println(new Client206().recursionToReverseList(t1));
    }


}
